Math 512: Finite Model Theory Monadic Σ_{1}^{1} and Hanf’s theorem

John Baldwin

February 7, 1997

Remark PTIME is closed under complement; it is open whether NP is closed under complement – thus whether Σ_{1}^{1} is closed under complement. We will show monadic Σ_{1}^{1} is not.

0.1 Definition. Let K be a class of L-structures. An n-ary global relation on K is a function Γ such that for each A, Γ(A) is an n-ary relation on A, which is preserved by isomorphism.

Examples: any logical formula; if R is a binary relations symbol, the transitive closure of R, connectivity is a 0-ary global relation on graphs.

0.2 Theorem. Connectivity is not monadic-Σ_{1}^{1}.

We will introduce considerable terminology to prove this result. Refer to Sections 1.3 and 1.4 of E and F.

0.3 Lemma. A ≡_{m} B if and only if there exists an m-back and forth between them. That is a sequence, ⟨I_{j}; j ≤ m⟩, such that

1. Every I_{j} is a nonempty set of partial isomorphisms between A and B.

2. (forth) If p ∈ I_{j+1} and a ∈ A − dom p, there is a q ∈ I_{j} with a ∈ dom q and q ⊇ p.

3. (back) If p ∈ I_{j+1} and b ∈ B − rng p, there is a q ∈ I_{j} with b ∈ rng q and q ⊇ p.

In general, if p ∈ I_{j}, | dom p| = m − j.

Application: In the language with binary relation. C_{r} ≡_{m} C_{s} if s, r ≥ 2^{m}. Let I_{j} = {p ∈ P art(C_{r}, C_{s}) : d_{j}(a, b) = d_{j}(p(a), p(b))} where d_{j}(a, b) is the distance from a to b if it is less than 2^{j+1} or else infinity.

We can extend this idea to an arbitrary relational structure by d(a, b) = 1 if for some \overline{a}, a, b ∈ \overline{a} and for some R, A ⊧ R(\overline{a}) and take lengths of paths.

In this sense, S(r, a) = {b : d(a, b) < r}. An r-sphere type of an element a is the isomorphism type of the r-sphere about a. S(r, \overline{a}) = ∪_{i}S(r, a_{i}).

Trivial case: only unary predicates. The r-sphere type of a is just which unary predicates hold and don’t hold of it. More generally, unary predicates don’t affect distance.

0.4 Theorem. (Hanf) Let A and B be structures such that the 3^{m}-spheres in A, B have less than e elements. Suppose also that for each n < 3^{m} and n-sphere type t:

1. A and B have the same number (< e · 3^{m}) of elements of n-sphere type t.

2. Both A and B have more than (e · 3^{m}) elements of n-sphere type t.

Proof. Let

I_{j} = \{p ∈ P art(C_{r}, C_{s}) : S(3^{j}, \overline{a}) ≈ S(3^{j}, p(\overline{a}))\}.

We must verify the back and forth; say forth. So suppose, ⟨\overline{a}, p(\overline{a})⟩ = p ∈ I_{j+1} and a ∈ A − dom p. Let π : S(3^{j+1}, \overline{a}) ≈ S(3^{j+1}, p(\overline{a}).

If a ∈ S(2 · 3^{j}, \overline{a}), S(3^{j}, \overline{a}a) ⊆ S(3^{j+1}, \overline{a}) and we let q(a) = π(a).

If a ∉ S(2 · 3^{j}, \overline{a}) then S(3^{j}, \overline{a}) ∩ S(3^{j}, a) = ∅. Let t be the 3^{j}-type of a. Clearly (since isomorphic under π), S(2 · 3^{j}, \overline{a}) and S(2 · 3^{j}, p(\overline{a})) contain the same number of elements with 3^{j}-type t and this number must be less than length of \overline{a} times e. So there must be a b ∉ S(2 · 3^{j}, p(\overline{a})) with 3^{j}-type t. Let q(a) = b.

Proof of 0.2. Suppose for contradiction that the Σ_{1}^{1}-formula ϕ with (first order) quantifier degee m axiomatized connectivity. Say ϕ contains unary predicates P_{1} … P_{r}. Note that if s > 2 · 3^{m} + 1, then each 3^{m}-sphere in C_{s} has exactly 2 · 3^{m} + 1 elements. Let i be number of isomorphism types of 3^{m} spheres in expansions of long cycles by r unary predicates. Let ℓ_{0} = (i + 1)(2 · 3^{m} + 1). If ℓ ≥ ℓ_{0}, (C_{ℓ}, P_{1} … P_{r}) contains disjoint and isomorphic 3^{m}-spheres.

Then any such (C_{ℓ}, P_{1} … P_{r}) ⊧ ϕ. We will construct (D_{ℓ}, P_{1} … P_{r}) which also satisfies ϕ but is not connected. Namely take a, b ∈ C_{ℓ}, such that S(3^{m}, a)∩S(3^{m}, b) = ∅. Suppose we have E(a^{−}, a and E(b^{−}, b) (with a^{−} and b^{−} in different intervals between a and b. Form D_{ℓ} by replacing the edge from b^{−} to b with one from b to a^{−} and the edge from a^{−} to a with one from a to b^{−}. Since S(3^{m}, a) ≈ S(3^{m}, b), (C_{ℓ}, P_{1} … P_{r}) and (D_{ℓ}, P_{1} … P_{r}) satisfy the hypotheses of Hanf’s theorem and are m-equivalent in (R, P_{1} … P_{n}).

Easily, the class of non-connected graphs is monadic Σ_{1}^{1}. So,

0.5 Theorem. Monadic Σ_{1}^{1} is not closed under complement.